L2-006 树的遍历

题目 L2-006 树的遍历

思路分析

https://www.bilibili.com/video/BV1u64y1Q7BH?vd_source=f90b3e1fec7a29aa578bf2c42517c160

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

const int N=35;

typedef struct BiTNode{
	int val;
	struct BiTNode *lchild,*rchild;
}BiTNod,*BiTree;

int n,in[N],post[N];

BiTree build_Tree(int in[],int l1,int r1,int post[],int l2,int r2){
	if(l1 > r1 || l2 > r2)	return NULL;
	BiTree root = new BiTNode;
	root -> val = post[r2];
	int tmp;
	for(int i=l1;i<=r1;i++){
		if(in[i]==post[r2]){
			tmp=i;
			break;
		}
	}
	root->lchild = build_Tree(in,l1,tmp-1,post,l2,l2+tmp-l1-1);
	root->rchild = build_Tree(in,tmp+1,r1,post,l2+tmp-l1,r2-1);
	return root;

}

void test(BiTree root){
	if(root){
		test(root->lchild);
		test(root->rchild);
		cout<<root->val<<" ";
	}
}

void bfs(BiTree root){
	if(!root)	return;
	queue<BiTree> q;
	q.push(root);
	bool is_first = true;
	while(q.size())	{
		auto tmp=q.front();
		if(is_first){
			cout<<tmp->val;
			is_first=false;
		}else{
			cout<<" "<<tmp->val;
		}
		q.pop();
		if(tmp->lchild)	q.push(tmp->lchild);
		if(tmp->rchild)	q.push(tmp->rchild);
	}
}

int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++)	cin>>post[i];
	for(int i=0;i<n;i++)	cin>>in[i];

	BiTree root = build_Tree(in,0,n-1,post,0,n-1);

//	test(root);

	bfs(root);

    return 0;
}

同类题型

视频讲解

⬅️ L2-005 集合相似度 🏠 00-天梯赛 ➡️ 二叉树